COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.cb Permutations 	(from Chapter II exercises)
C00011 ENDMK
C⊗;
.cb Permutations 	(from Chapter II exercises)

	By ``permutation on n letters'' we mean a one to one mapping
whose domain and range are a collection of n objects.
If f is a permutation on the collection C then each element of C 
is the image under f of exactly one element of C.  
For convenience we will imagine that C is the set {1,2,...n}.   

For example one permutation on 4 letters would be the mapping f where
f[1]=2, f[2]=4, f[3]=3 and f[4]=1.  We represent this schematically as

			/1 2 3 4\
		   f ~	\2 4 3 1/

We can also think of permutations as acting on lists.
If u is a list of length n and f is a permutation on {1,2...n} then
f permutes u into v where the ith element of u is the f[i]th element of
v.  We write this as f"u=v

For example if u is the list (A B C D) and v=f"u then A is the 
2nd element of v, B the 4th, C the 3rd, and D the first.  Thus

		f"(A B C D) = (D A C B)


Given two permutations f and g on C we can form the composition h=g@f
which is the result of first applying f then g.  Notice that h is also
a permutation.

For example with f as above and 

			/1 2 3 4\
		   g ~	\2 3 4 1/

then g@f[1] = g[f[1]] = g[2] = 3 and 

	       		/1 2 3 4\
		 g@f ~ 	\3 1 4 2/


Also

		g"(A B C D) = (D A B C)
	      g@f"(A B C D) = (B D A C)

Notice that we can compute g@f"u directly or by applying g to f"u.


Each permutation f on C has an inverse f- which is a permutation 
which when composed with f (in either order) gives the identity
map on C.  Thus 

			/1 2 3 4\
		  f- ~	\4 1 3 2/

			/1 2 3 4\
		Id{4} ~	\1 2 3 4/


and

		f@f- = f-@f = Id{4}


Another way to think of a permutation is by following the image of
a particular element of the domain under repeated application of the
permutation.  For f from above we have

		f: 1 -> 2 -> 4 -> 1 
		   3 -> 3

Notice that f partitions the domain in to disjoint subsets that
form cycles under the action of f.  These cycles completely characterize
the permutation and provides another means of representing a 
permutation.


We can think of the iteration (repeated application) of a permutation
as an operation on permutations.  A permutation applied 0 times is just
the identity operation.  If It[f,k] is the permutation
f applied k times then we have the following 

		It[f,0] = Id
		It[f,k+1] = f@It[f,k] = It[f,k]@f




We have given a schematic representation of permuatations above.
There are several ways of representing permutations on {1...n}
as data structures in LISP.  Here are some.


ALIST:  A permutation f is represented by a list
of pairs (i . f[i]).  In this representation we have

		f ~ ((1 . 2) (2 . 4) (3 . 3) (4 . 1))
		g ~ ((1 . 2) (2 . 3) (3 . 4) (4 . 1))
 	      g@f ~ ((1 . 3) (2 . 1) (3 . 4) (4 . 2))
	       f- ~ ((1 . 4) (2 . 1) (3 . 3) (4 . 2))


The order that the pairs appear in the list does not matter so we also
have
		f ~ ((3 . 3) (2 . 4) (4 . 1) (1 . 2))

SEQUENCE: as a list of numbers.  A permutation f is
represented by the list (f[1] f[2] ... f[n]).  Continuing the examples
above we represent f,g,g@f as lists as follows:

		f ~ (2 4 3 1)
		g ~ (2 3 4 1)
	      g@f ~ (3 1 4 2)
	       f- ~ (4 1 3 2)

CYCLES:  as a list of cycles.  A permutation is represented by
a list of the cycles formed by repeated application.  Thus


		f ~ ((1 2 4) (3))
		g ~ ((1 2 3 4))
 	      g@f ~ ((1 3 4 2))
	       f- ~ ((1 4 2) (3))


Cycles of length 1 can be omitted and the order of the cycles in the
list is unimportant.


Notice that each representation has advantages and disadvantages.
With lists the value f[i] is easy to compute (even easier if
we use 1 dimensional arrays).   With alists and cycles the inverse
is easy to compute.


Problems:  (R stands for one of the above representations)

Computing operations on permutations within a fixed representation.

For permutations represented as in R write programs to compute
the following operations:

Compose[g,f] represents g@f
Inverse[f] represents f-
Iterate[f,k] represents f repeated k times
Apply[f,u] is the result of applying f to the list u (as above).

For example in the SEQUENCE representation

Compose[(2 3 4 1),(2 4 3 1)] = (3 1 4 2)
Inverse[(2 4 3 1)] = (4 1 3 2)
Iterate[(2 4 3 1),0] = (1 2 3 4)
Iterate[(2 4 3 1),2] = (4 1 3 2)
Apply[(2 4 3 1),(A B C D)] = (D A C B)

Converting from one representation to another.

For R1,R2 from the above list of representations the program
Convert[R1,R2,f] converts f from representation R1 to R2.
(If there are several structures representing a given permutation
 any one will do.  You may wish to settle on a canonical representative.)

For example:
    Convert[CYCLES,SEQUENCE,((1 2 4) (3))] = (2 4 3 1)
    Convert[SEQUENCE,ALIST,(2 4 3 1)] = ((1 . 2) (2 . 4) (3 . 3) (4 . 1))

#. ⊗isperm1[pi,n] (⊗⊗isperm2[pi,n]⊗) is true just if the list ⊗pi represents 
a permutation on ⊗n objects according to $REP1 ($$REP2$).

#. ⊗sameperm2[pi1,pi2] is true if and only if ⊗pi1 and ⊗pi2 represent the same
permutation.  (Note that the representation by $REP2 is not unique
while in $REP1 it is.)

Cycling

#.  ⊗rcycle[u]  is obtained from the list ⊗u by moving the
last element to the first position.  Thus

⊗⊗⊗rcycle[$$(A B C D)$] = $$(D A B C)$⊗.

#. ⊗lcycle[u]  is obtained from the list ⊗u by moving the
first element to the last position.  Thus

⊗⊗⊗lcycle[$$(A B C D)$] = $$(B C D A)$⊗. 


For representation R

rc[n] represents the permutation on n letters that implements rcycle
Thus Apply[rc[lenght u],u] = rcycle[u] 

lc[n] represents the permutation on n letters that implements lcycle
Thus Apply[lc[lenght u],u] = lcycle[u]